{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Lecture-03 Dynamic Programming"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 保存对应的长度的价格\n",
    "\n",
    "original_price = [1, 5, 8, 9, 10, 17, 18, 20, 24, 30, 33] # 添加长度11的价格33"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Length i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11\n",
    ":-- | :--: | :--: |:--: | :--: |:--: |:--: |:--: |:--: |:--: |:--: | :--: \n",
    "Price $p_i$ | 1 | 5 |8 | 9 | 10 | 17 | 18 | 20 | 24 | 30 | 33"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 使用`defaultdict`存储长度与价格的字典，以避免万一输入长度在表里没有的话，不至于报错"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "price = defaultdict(int)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "for idx, p in enumerate(original_price):\n",
    "    price[idx+1] = p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "price[12]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 通过递归的方法获取到每一个长度的最佳价格的分割 - Get the max splitting by enumerate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def r(n):\n",
    "    \"\"\"Get the optimal revenue given length n\"\"\"\n",
    "    return max([price[n]] + [r(i) + r(n-i) for i in range(1, n)]) # n 分割为 i和n-i"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$ revenue(3) = max(price(3), revenue(2) + revenue(1))$$\n",
    "\n",
    "$$ revenue(4) = max(price(4), revenue(3) + revenue(1),  revenue(2) + revenue(2))$$\n",
    "\n",
    "```\n",
    "n = 100\n",
    "revenue(n) -- revenue(n-1), revenue(1)\n",
    "           -- revenue(n-2), revenue(2)\n",
    "           -- revenue(n-3), revenue(3)\n",
    "           ....\n",
    "```\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 获取长度4的最佳分割价格\n",
    "r(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "30"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### 这里有一个问题，就是求的长度越长的时候，函数执行的时间就越长，原因是在计算时，比如5拆分为3+2，会计算一遍3和2, 4拆分为3+1，又会再计算一遍3，凡是拆分中包含3的都会再计算一遍，所以函数时间复杂度就特别长。\n",
    "\n",
    "```\n",
    "n = 100\n",
    "revenue(n) -- revenue(n-1), revenue(1)\n",
    "           -- revenue(n-2), revenue(2)\n",
    "           -- revenue(n-3), revenue(3)\n",
    "           ....\n",
    "```\n",
    "\n",
    "```\n",
    "T(f(n)) = T(f(n-1)) + T(f(n-2)) + .. T(f(2))\n",
    "f(n-1) = f(n-2) * C\n",
    "f(n-2) = f(n-3) * C\n",
    "...\n",
    "f(1) = C\n",
    "\n",
    "f(n) = C^n\n",
    "```\n",
    "\n",
    "```\n",
    "T(f(n)) = (n-1)f(i)\n",
    "f(n-1) = (n-2)f(i)\n",
    "f(n-2) = (n-2)f(i)\n",
    "...\n",
    "f(1) = C\n",
    "\n",
    "(n-1)^n\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 如果优化？\n",
    "\n",
    "最简单的一个方法就是使用一个中间变量存储计算结果，在后面的计算中，先从中间缓存中查询，如果已经存在中间缓存中，就直接取出结果，如果不存在缓存中，计算后存入缓存中就行。\n",
    "\n",
    "使用缓存的方法，可以使计算斐波拉契数列变得更简单。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# fib\n",
    "\n",
    "def fib(n):\n",
    "    if n<=1: return n\n",
    "    else:\n",
    "        return fib(n-1) + fib(n-2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "时间复杂度：\n",
    "\n",
    "```\n",
    "f(n) = f(n/2) + f(n/2) \n",
    "--> nlogn\n",
    "\n",
    "f(n) = f(n-1) + f(n-2) + f(n-3) + ..f(1)\n",
    "--> T(n) => O(n!)\n",
    "\n",
    "f(n) = f(n/2) + f(n/2) + f(n-2) + f(n-3) \n",
    "--> O(nlogn) + O(n!)\n",
    "--> O(n!)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 采用 `merge sort` -> T(n) = NlogN"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fib(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 使用装饰器函数来存储中间变量值"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "比如一个复杂计算函数，如果想要获取到它的执行时间：\n",
    "~~~python\n",
    "def complexity_computing(n):\n",
    "    time.sleep(0.5)\n",
    "    return n**2\n",
    "\n",
    "~~~\n",
    "\n",
    "在代码中使用装饰器函数来实现的话有如下优点：\n",
    "\n",
    "1. 不需要把每一个需要打印时间的函数都修改代码，是在函数之外加的功能\n",
    "2. 要不要把调用这个函数的其他函数进行修改"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import wraps\n",
    "\n",
    "# 定义获取运行时间的装饰器函数\n",
    "def get_time(f):\n",
    "    \"\"\" I could get a function's time \"\"\"\n",
    "    @wraps(f)\n",
    "    def wrap(*args, **kwargs):\n",
    "        \"\"\"这里才是获取时间的\"\"\"\n",
    "        start = time.time()\n",
    "        result = f(*args, **kwargs)\n",
    "        end = time.time()\n",
    "        print('Used time = {}'.format(end - start))\n",
    "        return result\n",
    "    return wrap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Used time = 0.5006904602050781\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "100"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@get_time\n",
    "def complexity_computing(n):\n",
    "    time.sleep(0.5)\n",
    "    return n**2\n",
    "\n",
    "complexity_computing(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Used time = 0.5008993148803711\n",
      "Used time = 0.5008993148803711\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "100"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 另一种调用方式\n",
    "get_time(complexity_computing)(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "通过上面的例子介绍，可以通过装饰器函数进行存储中间计算缓存。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def memo(f):\n",
    "    \"\"\"中间计算缓存\"\"\"\n",
    "    memo.already_computed = {}\n",
    "    # lru_cache: cache_size : least_recent_used\n",
    "    @wraps(f)\n",
    "    def _wrap(arg):\n",
    "        if arg in memo.already_computed:\n",
    "            result = memo.already_computed[arg]\n",
    "        else:\n",
    "            result = f(arg)\n",
    "            memo.already_computed[arg] = result\n",
    "        return result\n",
    "    return _wrap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "@memo\n",
    "def r(n):\n",
    "    return max([price[n]] + [r(i) + r(n-i) for i in range(1, n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "30"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Used time = 0.0\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "90"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_time(r)(30)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "120"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r(40)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在执行过程中可以明显的看出通过使用中间缓存计算结果，运行时间明显缩短。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "把中间结果存起来，然后加快计算的过程。 - “不断查表法”\n",
    "\n",
    "Programming == 写、查表\n",
    "\n",
    "Dynamic == 不断地\n",
    "\n",
    "Dynamic Programming -> 可以把一个问题分割成子问题，然后呢，子问题又有重复的这种问题，就适合用 Dynamic Programming。\n",
    "\n",
    "如何通过这种方法来解决 Cut Road问题？\n",
    "\n",
    "解决方法是使用一个中间变量来存储取得最大收益的切割结果。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution = {}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "@memo\n",
    "def r2(n):\n",
    "    \"\"\"\n",
    "    Params:\n",
    "    ------\n",
    "    n -> length of iron to cut.\n",
    "    \n",
    "    Return:\n",
    "    ------\n",
    "    the max revenue(收益).\n",
    "    \"\"\"\n",
    "    revenue_left_split_right_notes = [(price[n], 0, n)] # 所有的（价格，左边切割长度，右边切割长度）组成的列表\n",
    "    for i in range(1, n):\n",
    "        revenue_left_split_right_notes.append((r2(i) + r2(n-i), # 切割后的总的价格收益\n",
    "                                               n-i, # 左边切割的长度\n",
    "                                               i) # 右边切割的长度\n",
    "                                             )\n",
    "    max_price, left_split, right_split = max(revenue_left_split_right_notes, key=lambda x: x[0]) # 按价格进行排序后去最高收益\n",
    "\n",
    "    solution[n] = (left_split, right_split) # 并保存切割结果\n",
    "        \n",
    "    return max_price"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "price[123]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "369"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r2(123)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1: (0, 1),\n",
       " 2: (0, 2),\n",
       " 3: (0, 3),\n",
       " 4: (2, 2),\n",
       " 5: (3, 2),\n",
       " 6: (0, 6),\n",
       " 7: (0, 7),\n",
       " 8: (6, 2),\n",
       " 9: (6, 3),\n",
       " 10: (0, 10),\n",
       " 11: (0, 11),\n",
       " 12: (10, 2),\n",
       " 13: (11, 2),\n",
       " 14: (11, 3),\n",
       " 15: (13, 2),\n",
       " 16: (10, 6),\n",
       " 17: (11, 6),\n",
       " 18: (16, 2),\n",
       " 19: (17, 2),\n",
       " 20: (10, 10),\n",
       " 21: (11, 10),\n",
       " 22: (11, 11),\n",
       " 23: (21, 2),\n",
       " 24: (22, 2),\n",
       " 25: (22, 3),\n",
       " 26: (20, 6),\n",
       " 27: (21, 6),\n",
       " 28: (22, 6),\n",
       " 29: (27, 2),\n",
       " 30: (20, 10),\n",
       " 31: (21, 10),\n",
       " 32: (22, 10),\n",
       " 33: (22, 11),\n",
       " 34: (32, 2),\n",
       " 35: (33, 2),\n",
       " 36: (33, 3),\n",
       " 37: (31, 6),\n",
       " 38: (32, 6),\n",
       " 39: (33, 6),\n",
       " 40: (30, 10),\n",
       " 41: (31, 10),\n",
       " 42: (32, 10),\n",
       " 43: (33, 10),\n",
       " 44: (33, 11),\n",
       " 45: (43, 2),\n",
       " 46: (44, 2),\n",
       " 47: (44, 3),\n",
       " 48: (42, 6),\n",
       " 49: (43, 6),\n",
       " 50: (40, 10),\n",
       " 51: (41, 10),\n",
       " 52: (42, 10),\n",
       " 53: (43, 10),\n",
       " 54: (44, 10),\n",
       " 55: (44, 11),\n",
       " 56: (54, 2),\n",
       " 57: (55, 2),\n",
       " 58: (55, 3),\n",
       " 59: (53, 6),\n",
       " 60: (50, 10),\n",
       " 61: (51, 10),\n",
       " 62: (52, 10),\n",
       " 63: (53, 10),\n",
       " 64: (54, 10),\n",
       " 65: (55, 10),\n",
       " 66: (55, 11),\n",
       " 67: (65, 2),\n",
       " 68: (66, 2),\n",
       " 69: (66, 3),\n",
       " 70: (60, 10),\n",
       " 71: (61, 10),\n",
       " 72: (62, 10),\n",
       " 73: (63, 10),\n",
       " 74: (64, 10),\n",
       " 75: (65, 10),\n",
       " 76: (66, 10),\n",
       " 77: (66, 11),\n",
       " 78: (76, 2),\n",
       " 79: (77, 2),\n",
       " 80: (70, 10),\n",
       " 81: (71, 10),\n",
       " 82: (72, 10),\n",
       " 83: (73, 10),\n",
       " 84: (74, 10),\n",
       " 85: (75, 10),\n",
       " 86: (76, 10),\n",
       " 87: (77, 10),\n",
       " 88: (77, 11),\n",
       " 89: (87, 2),\n",
       " 90: (80, 10),\n",
       " 91: (81, 10),\n",
       " 92: (82, 10),\n",
       " 93: (83, 10),\n",
       " 94: (84, 10),\n",
       " 95: (85, 10),\n",
       " 96: (86, 10),\n",
       " 97: (87, 10),\n",
       " 98: (88, 10),\n",
       " 99: (88, 11),\n",
       " 100: (90, 10),\n",
       " 101: (91, 10),\n",
       " 102: (92, 10),\n",
       " 103: (93, 10),\n",
       " 104: (94, 10),\n",
       " 105: (95, 10),\n",
       " 106: (96, 10),\n",
       " 107: (97, 10),\n",
       " 108: (98, 10),\n",
       " 109: (99, 10),\n",
       " 110: (100, 10),\n",
       " 111: (101, 10),\n",
       " 112: (102, 10),\n",
       " 113: (103, 10),\n",
       " 114: (104, 10),\n",
       " 115: (105, 10),\n",
       " 116: (106, 10),\n",
       " 117: (107, 10),\n",
       " 118: (108, 10),\n",
       " 119: (109, 10),\n",
       " 120: (110, 10),\n",
       " 121: (111, 10),\n",
       " 122: (112, 10),\n",
       " 123: (113, 10)}"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 如何解析 solution?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def parse_solution(n):\n",
    "    left_split, right_split = solution[n]\n",
    "    \n",
    "    if left_split == 0: return [right_split]\n",
    "    return parse_solution(left_split) + parse_solution(right_split)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[11, 11, 11, 2]"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "parse_solution(35)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1005"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r2(335)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[11,\n",
       " 11,\n",
       " 11,\n",
       " 11,\n",
       " 11,\n",
       " 10,\n",
       " 10,\n",
       " 10,\n",
       " 10,\n",
       " 10,\n",
       " 10,\n",
       " 10,\n",
       " 10,\n",
       " 10,\n",
       " 10,\n",
       " 10,\n",
       " 10,\n",
       " 10,\n",
       " 10,\n",
       " 10,\n",
       " 10,\n",
       " 10,\n",
       " 10,\n",
       " 10,\n",
       " 10,\n",
       " 10,\n",
       " 10,\n",
       " 10,\n",
       " 10,\n",
       " 10,\n",
       " 10,\n",
       " 10,\n",
       " 10]"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "parse_solution(335)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 动态规划解决问题的3个步骤\n",
    "1. 识别拆分子问题\n",
    "2. 去除重复子问题的\n",
    "3. 解析问题求解过程"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 编辑距离\n",
    "<b>最小编辑距离(Minimum Edit Distance, MED)</b>又称为<b>Levenshtein距离</b>，是指两个字符串之间，由一个转成另一个所需要的最少编辑操作次数。允许的编辑(距离都为 1)操作包括：\n",
    "1. 替换(substitution) - 将一个字符替换为另一个字符\n",
    "2. 插入(insert) - 插入一个字符（任意位置）\n",
    "3. 删除(delete) - 任意位置删除一个字符\n",
    "~~~python\n",
    "Distance(i, j) = min(D(i-1, j)+1,\n",
    "                     D(i, j-1)+1,\n",
    "                     D(i-1, j-1)+2 if string1[i] != string2[j] else D(i-1, j-1)\n",
    "                     )\n",
    "~~~\n",
    "\n",
    "解释：\n",
    "~~~python\n",
    "D(0, 0) = 0\n",
    "D(i, 0) = D(i-1, 0) + del[x[i]]; 1 < i <= N  \n",
    "D(0, j) = D(0, j-1) + ins[y(j)]; 1 < j <= M  \n",
    "\n",
    "# 递归方程\n",
    "D(i, j) = min(D(i-1, j) + del[x[i]], # 纵向操作\n",
    "              D(i, j-1) + ins[y[j]], # 横向操作\n",
    "              D(i-1, j-1) + sub[x(i), y(j)]\n",
    "~~~\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 直接使用functools中提供的 lru_cache装饰器\n",
    "\n",
    "from functools import lru_cache "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "edit_solution = {}\n",
    "\n",
    "@lru_cache(maxsize=2**10)\n",
    "def edit_distance(string1, string2):\n",
    "    \"\"\"\n",
    "    Distance(i, j) = min(D(i-1, j)+1,\n",
    "                         D(i, j-1)+1,\n",
    "                         D(i-1, j-1)+2 if string1[i] != string2[j] else D(i-1, j-1))\n",
    "    \"\"\"\n",
    "    if len(string1) == 0: return len(string2)\n",
    "    if len(string2) == 0: return len(string1)\n",
    "    \n",
    "    tail_s1 = string1[-1]\n",
    "    tail_s2 = string2[-1]\n",
    "    \n",
    "    candicates = [\n",
    "        (edit_distance(string1[:-1], string2) + 1, 'DEL {}'.format(tail_s1)), # string1 delete tail\n",
    "        (edit_distance(string1, string2[:-1]) + 1, 'ADD {}'.format(tail_s2)), # string1 add string2 tail\n",
    "    ]\n",
    "    \n",
    "    if tail_s1 == tail_s2:\n",
    "        both_forward = (edit_distance(string1[:-1], string2[:-1]) + 0, '')\n",
    "    else:\n",
    "        both_forward = (edit_distance(string1[:-1], string2[:-1]) + 1, 'Sub {} => {}'.format(tail_s1, tail_s2)) # tail_s1替换tail_s2\n",
    "    candicates.append(both_forward)\n",
    "\n",
    "    min_distance, operation = min(candicates, key=lambda x: x[0])\n",
    " \n",
    "    edit_solution[(string1, string2)] = operation\n",
    "    return min_distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "edit_distance('test', 'tets')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{('t', 't'): '',\n",
       " ('t', 'te'): 'ADD e',\n",
       " ('t', 'tet'): 'ADD t',\n",
       " ('t', 'tets'): 'ADD s',\n",
       " ('te', 't'): 'DEL e',\n",
       " ('te', 'te'): '',\n",
       " ('te', 'tet'): 'ADD t',\n",
       " ('te', 'tets'): 'ADD s',\n",
       " ('tes', 't'): 'DEL s',\n",
       " ('tes', 'te'): 'DEL s',\n",
       " ('tes', 'tet'): 'Sub s => t',\n",
       " ('tes', 'tets'): '',\n",
       " ('test', 't'): 'DEL t',\n",
       " ('test', 'te'): 'DEL t',\n",
       " ('test', 'tet'): '',\n",
       " ('test', 'tets'): 'DEL t'}"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "edit_solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### TODO - How to parse the edit solution?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "def parse_edit_solution(string1: str, string2: str, edit_solution: dict):\n",
    "    ret = []\n",
    "    n = len(string1)\n",
    "    m = len(string2)\n",
    "    if n > m:\n",
    "        ret + ['DEL {}'.format(string1[m:])]\n",
    "    if n < m:\n",
    "        ret + ['ADD {}'.format(string2[n:])]\n",
    "    idx = max(n, m)\n",
    "    for i in range(idx, 0, -1):\n",
    "        if string1[:i] != string2[:i]:\n",
    "            solution = edit_solution[(string1[:i], string2[:i])]\n",
    "            if solution == '':\n",
    "                pass\n",
    "            else:\n",
    "                ret.append(solution)\n",
    "            continue\n",
    "        else:\n",
    "            solution = edit_solution[(string1[:i], string2[:i+2])]\n",
    "            if solution == '':\n",
    "                pass\n",
    "            else:\n",
    "                ret.append(solution)\n",
    "            break\n",
    "    return ret   \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "test 通过  DEL t --> Sub s => t --> ADD s  转换为 tets\n"
     ]
    }
   ],
   "source": [
    "print(\"test 通过 \", ' --> '.join(parse_edit_solution('test', 'tets', edit_solution)), ' 转换为 tets')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "edit_solution = {}\n",
    "\n",
    "edit_distance('intention', 'execution')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "intention 通过  ADD u --> ADD c --> Sub t => e --> Sub n => x --> Sub i => e  转换为 execution\n"
     ]
    }
   ],
   "source": [
    "print(\"intention 通过 \", ' --> '.join(parse_edit_solution('intention', 'execution', edit_solution)), \" 转换为 execution\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem Case 3: Pinyin Auto Correction Problem - 拼音自动纠错"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "chinese_dataset = 'article_9k.txt'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "CHINESE_CHARACTERS = open(chinese_dataset, encoding='utf-8').read()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'此外自本周6月12日'"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "CHINESE_CHARACTERS[:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pinyin"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'ni hao'"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pinyin.get('你好', format='strip', delimiter=\" \")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "@get_time\n",
    "def chinese_to_pinyin(character, delimiter=' '):\n",
    "    return pinyin.get(character, format='strip', delimiter=delimiter)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'ni shuo shi yao'"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "chinese_to_pinyin('你说什么')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['ni'], ['shuo'], ['shen'], ['me']]"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import pypinyin\n",
    "\n",
    "pypinyin.pinyin('你说什么', pypinyin.NORMAL)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "@get_time\n",
    "def chinese_to_pinyin_v2(character):\n",
    "    s = []\n",
    "    for i in pypinyin.pinyin(character, pypinyin.NORMAL):\n",
    "        s += i\n",
    "    return ' '.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Used time = 18.685651779174805\n"
     ]
    }
   ],
   "source": [
    "CHINESE_PINYIN_COPYS = chinese_to_pinyin(CHINESE_CHARACTERS)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'ci wai zi ben zhou 6 yue 12 ri qi chu xiao mi shou ji 6 deng 15 kuan ji xing wai qi yu ji xing yi za'"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "CHINESE_PINYIN_COPYS[:100]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "\n",
    "def tokens(text):\n",
    "    \"\"\"List all the pinyin characters\"\"\"\n",
    "    return re.findall('[a-z]+', text.lower())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 150,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['ci', 'wai', 'zi', 'ben', 'zhou', 'yue', 'ri', 'qi', 'chu', 'xiao']"
      ]
     },
     "execution_count": 150,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "CLEAN_PINYIN = tokens(CHINESE_PINYIN_COPYS)\n",
    "CLEAN_PINYIN[:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter, defaultdict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 151,
   "metadata": {},
   "outputs": [],
   "source": [
    "PINYIN_COUNT = Counter(CLEAN_PINYIN)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('shi', 860634),\n",
       " ('de', 809887),\n",
       " ('n', 691114),\n",
       " ('yi', 682478),\n",
       " ('ji', 645276),\n",
       " ('guo', 430042),\n",
       " ('zhong', 409418),\n",
       " ('zhi', 398612),\n",
       " ('xin', 359619),\n",
       " ('li', 355441)]"
      ]
     },
     "execution_count": 152,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "PINYIN_COUNT.most_common(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 寻找最可能正确的拼音\n",
    "def correct(word):\n",
    "    \"\"\"Find the most possible pinyin based on edit distance\"\"\"\n",
    "    # Prefer edit distance 0, then 1, then 2; otherwise default to word itself\n",
    "    \n",
    "    candicates = (known(edits0(word)) or\n",
    "                  known(edits1(word)) or\n",
    "                  known(edits2(word)) or\n",
    "                  [word])\n",
    "    return max(candicates, key=PINYIN_COUNT.get) # return the most possible 根据字典中出现次数的多少进行排序，返回出现次数最多的"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {},
   "outputs": [],
   "source": [
    "def known(words):\n",
    "    \"\"\"\n",
    "    @param: words - list\n",
    "    @return: the pinyin words we have noticed.\n",
    "    \"\"\"\n",
    "    return {w for w in words if w in PINYIN_COUNT}\n",
    "\n",
    "def edits0(word):\n",
    "    \"\"\"Return all strings that are zero edits away from word (i.e. just word itself)\"\"\"\n",
    "    return {word}\n",
    "\n",
    "def edits2(word):\n",
    "    \"\"\"Return all strings that are two edits away from this pinyin\"\"\"\n",
    "    return {e2 for e1 in edits1(word) for e2 in edits1(e1)} # 与word编辑距离为1的拼音为的编辑距离为1的拼音"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 如何实现 edits1()?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 155,
   "metadata": {},
   "outputs": [],
   "source": [
    "alphabet = 'abcdefghijklmnopqrstuvwxyz'\n",
    "\n",
    "# 以下的编辑距离都是 1\n",
    "\n",
    "# 删除一个字符\n",
    "def get_deletes(pairs):\n",
    "    return [a+b[1:] for (a, b) in pairs if b]\n",
    "\n",
    "# 两个字符置换位置 - 置换的编辑距离应该为2，方便操作，这里默认为1\n",
    "def get_transposes(pairs):\n",
    "    return [a + b[1] + b[0] + b[2:] for (a, b) in pairs if len(b) > 1]\n",
    "\n",
    "\n",
    "# 替换一个字符\n",
    "def get_replaces(pairs):\n",
    "    return [a + c + b[1:] for (a, b) in pairs for c in alphabet if b]\n",
    "\n",
    "# 插入一个字符\n",
    "def get_inserts(pairs):\n",
    "    ret = [a + c + b for (a, b) in pairs for c in alphabet]\n",
    "    return ret\n",
    "\n",
    "\n",
    "def edits1(word):\n",
    "    \"\"\"\n",
    "    Return all strings that are one edit away from this pinyin.\n",
    "    \"\"\"\n",
    "    pairs = splits(word) # 对word进行拆分得到所有可能的拼音组合\n",
    "    deletes = get_deletes(pairs)\n",
    "    transposes = get_transposes(pairs)\n",
    "    replaces = get_replaces(pairs)\n",
    "    inserts = get_inserts(pairs)\n",
    "    return set(deletes + transposes + replaces + inserts)\n",
    "\n",
    "def splits(word):\n",
    "    \"\"\"Return a list of all possible (first, rest) pairs that comprise pinyin.\"\"\"\n",
    "    return [(word[:i], word[i:]) for i in range(len(word)+1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 156,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('', 'nen'), ('n', 'en'), ('ne', 'n'), ('nen', '')]"
      ]
     },
     "execution_count": 156,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "splits('nen')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 157,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'pinyin'}"
      ]
     },
     "execution_count": 157,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "edits0('pinyin')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 158,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'neng'"
      ]
     },
     "execution_count": 158,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "correct('negn')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 159,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'qing'"
      ]
     },
     "execution_count": 159,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "correct('qinng')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 160,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(95699, 241741)"
      ]
     },
     "execution_count": 160,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "PINYIN_COUNT['qing'], PINYIN_COUNT['xing']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 161,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['inyin', 'pnyin', 'piyin', 'pinin', 'pinyn', 'pinyi']"
      ]
     },
     "execution_count": 161,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_deletes(splits('pinyin'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 162,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['ipnyin', 'pniyin', 'piynin', 'piniyn', 'pinyni']"
      ]
     },
     "execution_count": 162,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_transposes(splits('pinyin'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 163,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'bin',\n",
       " 'jin',\n",
       " 'lin',\n",
       " 'min',\n",
       " 'nin',\n",
       " 'pan',\n",
       " 'pen',\n",
       " 'pie',\n",
       " 'pin',\n",
       " 'qin',\n",
       " 'xin',\n",
       " 'yin'}"
      ]
     },
     "execution_count": 163,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "known(get_replaces(splits('pin'))) # 取出'pin'进行替换后的所有的拼音中的存在于字典中拼音"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 164,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'pian', 'ping'}"
      ]
     },
     "execution_count": 164,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "known(get_inserts(splits('pin')))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 165,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'nin', 'lin', 'jin', 'pen', 'qin', 'xin', 'pie', 'yin', 'bin', 'pian', 'pi', 'ping', 'pan', 'min', 'pin'}\n"
     ]
    }
   ],
   "source": [
    "print(known(edits1('pin')))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 166,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'jin', 'ai', 'bing', 'mie', 'bian', 'bin', 'pian', 'hun', 'di', 'lun', 'mi', 'ni', 'ting', 'yun', 'xun', 'diu', 'si', 'lian', 'ying', 'min', 'ben', 'jun', 'ken', 'peng', 'pen', 'nen', 'xiu', 'qin', 'tan', 'san', 'bi', 'pou', 'zen', 'tie', 'po', 'fen', 'nin', 'ming', 'qie', 'xian', 'qiu', 'gan', 'kan', 'can', 'ban', 'dun', 'kun', 'hen', 'niu', 'jian', 'jiu', 'xi', 'lie', 'lan', 'tun', 'fan', 'pao', 'xia', 'gun', 'pi', 'man', 'lia', 'gen', 'han', 'zan', 'qia', 'ling', 'ji', 'tian', 'bie', 'pei', 'mian', 'ti', 'die', 'dian', 'miu', 'qi', 'qian', 'liu', 'pu', 'jing', 'lin', 'en', 'xin', 'piao', 'sun', 'men', 'run', 'dan', 'i', 'pang', 'cen', 'ren', 'pai', 'ran', 'xie', 'nan', 'pa', 'zi', 'cun', 'xing', 'ding', 'pie', 'qing', 'nie', 'p', 'jia', 'n', 'nian', 'jie', 'pan', 'sen', 'pin', 'li', 'yi', 'dia', 'an', 'ci', 'ping', 'ri', 'wen', 'ning', 'yin', 'yan', 'qun', 'zun', 'wan'}\n"
     ]
    }
   ],
   "source": [
    "print(known(edits2('pin')))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 167,
   "metadata": {},
   "outputs": [],
   "source": [
    "def edits3(word):\n",
    "    return {e3 for e2 in edits2(word) for e3 in edits1(e2)}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 168,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'ai', 'zou', 'pian', 'hai', 'xu', 'nang', 'lei', 'h', 'ben', 'le', 'da', 'pen', 'peng', 'ka', 'po', 'wang', 'gou', 'cuo', 'qiu', 'ku', 'e', 'gei', 'jiu', 'dao', 'lu', 'chi', 'tui', 'teng', 'deng', 'pao', 'jiang', 'leng', 'zhi', 'na', 'neng', 'man', 'cai', 'gen', 'lai', 'suo', 'u', 'pei', 'tu', 'ge', 'miu', 'jing', 'ju', 'pu', 'mu', 'gang', 'piao', 'yao', 'i', 'cen', 'se', 'hua', 'nai', 'nei', 'pa', 'xing', 'ding', 'ruo', 'mai', 'tiao', 'chu', 'nian', 'dia', 'rao', 'wai', 'wa', 'q', 'fang', 'sha', 'wen', 'sao', 'zun', 'bang', 'n', 'xue', 'wan', 'sa', 're', 'reng', 'di', 'la', 'kui', 'x', 'nong', 'diu', 'diao', 'si', 'lian', 'ying', 'bu', 'za', 'jue', 'xiu', 'tan', 'mao', 'hong', 'san', 'dang', 'sou', 'ga', 'gui', 'fo', 'fei', 'nuo', 'weng', 'xiao', 'qiang', 'hao', 'gu', 'dun', 'zhun', 'yong', 'jian', 'xi', 'r', 'ye', 'bei', 'xia', 'zang', 'huo', 'shi', 'zhan', 'keng', 'pi', 'geng', 'lia', 'de', 'yue', 'luan', 'su', 'ao', 'bo', 'han', 'cang', 'j', 'chen', 'bai', 'gao', 'liu', 'en', 'long', 'hui', 'er', 'ou', 'song', 'duo', 'ren', 'kou', 'zha', 'nve', 'cun', 'tang', 'nie', 'p', 'ha', 'lang', 'fa', 'pin', 'zuan', 'a', 'o', 'ping', 'cou', 'cha', 'jin', 'bing', 'nao', 'mie', 'bian', 'bin', 'she', 'ni', 'xun', 'tai', 'du', 'jun', 'qu', 'bi', 'pou', 'bao', 'zhen', 't', 'zen', 'tao', 'te', 'gai', 'nin', 'ming', 'ya', 'he', 'qie', 'tuan', 'gong', 'niao', 'kan', 'kong', 'zao', 'can', 'ban', 'kuo', 'zei', 'c', 'niu', 'lie', 'sai', 'cu', 'fan', 'kang', 'lve', 'b', 'ba', 'y', 'nu', 'rang', 'gun', 'w', 'g', 'lv', 'yo', 'cui', 'zhe', 'yuan', 'liang', 'qia', 'tian', 'bie', 'mian', 'mei', 'zui', 'shen', 'dian', 'yang', 'lou', 'gua', 'run', 'dan', 'kao', 'luo', 'shan', 'ran', 'xiong', 'dou', 'xie', 'nan', 'ruan', 's', 'pie', 'qing', 'zai', 'dai', 'ang', 'sui', 'huan', 'zu', 'you', 'jia', 'xuan', 'cuan', 'hu', 'sen', 'cao', 'guan', 'liao', 'dui', 'ce', 'ri', 'kua', 'ning', 'yin', 'yan', 'niang', 'feng', 'ne', 'xiang', 'mou', 'rui', 'v', 'jiao', 'hun', 'lun', 'kai', 'mi', 'quan', 'ting', 'yun', 'fou', 'sang', 'suan', 'min', 'tong', 'tuo', 'ken', 'hang', 'nen', 'zong', 'guo', 'qin', 'duan', 'juan', 'tie', 'yu', 'biao', 'fen', 'z', 'xian', 'chan', 'ceng', 'gan', 'k', 'qiong', 'hen', 'kun', 'kuan', 'meng', 'lao', 'ze', 'lan', 'tun', 'nuan', 'miao', 'nv', 'heng', 'ru', 'mo', 'd', 'wei', 'm', 'chun', 'zan', 'ling', 'ji', 'dong', 'rong', 'wo', 'cong', 'zeng', 'fu', 'che', 'ti', 'seng', 'die', 'qian', 'qi', 'ma', 'lin', 'jiong', 'xin', 'sun', 'l', 'men', 'mang', 'rou', 'pang', 'hou', 'pai', 'wu', 'zi', 'ke', 'shun', 'f', 'zuo', 'tou', 'jie', 'pan', 'li', 'yi', 'zhu', 'an', 'ta', 'ci', 'que', 'qiao', 'hei', 'ca', 'qun', 'shu', 'beng'}\n"
     ]
    }
   ],
   "source": [
    "print(known(edits3('pin')))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 是时候展示真正的技术了"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 169,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'yin'"
      ]
     },
     "execution_count": 169,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "correct('yin')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 170,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'ying'"
      ]
     },
     "execution_count": 170,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "correct('yign')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`correct`函数只能一次纠正一个拼音，下面封装一个可以对一句话(拼音直接使用空格隔开)中的所有拼音进行纠正的函数！"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 171,
   "metadata": {},
   "outputs": [],
   "source": [
    "def correct_sequence_pinyin(text_pinyin):\n",
    "    return ' '.join(map(correct, text_pinyin.split())) # 使用`map`函数对序列中的所有元素进行correct操作"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'zhe shi yi ge ce shi'"
      ]
     },
     "execution_count": 172,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "correct_sequence_pinyin('zhe sih yi ge ce sho')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 173,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(277726, 430042)"
      ]
     },
     "execution_count": 173,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "PINYIN_COUNT['you'], PINYIN_COUNT['guo']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 因为`correct_sequence_pinyin`中调用的`correct`函数是按出现频次来选择拼音的，没有考虑上下文关系，所以下面的句子中会把`yuo`修正为出现频次较多的`guo`。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 174,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'zhe ge guo dian ren gong zhi neng de yi si'"
      ]
     },
     "execution_count": 174,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "correct_sequence_pinyin(\"zhe ge yuo dien ren gnong zhi negn de yi si\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 175,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'wo xiang shang qing hua da xue'"
      ]
     },
     "execution_count": 175,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "correct_sequence_pinyin('wo xiang shang qinng hua da xeu')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 如果所有的拼音是连起来的话就使用上面的函数就无法完成修正"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 176,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'woxiangshangqinnghuadaxeu'"
      ]
     },
     "execution_count": 176,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "correct_sequence_pinyin('woxiangshangqinnghuadaxeu')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 思考题 - homework? 如何在不带空格的时候完成自动修正？ --> 如果完成拼音的自动分割?\n",
    "\n",
    "#### 提示：使用语言模型！ - 通过概率判断"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 177,
   "metadata": {},
   "outputs": [],
   "source": [
    "all_pinyin_count = sum(PINYIN_COUNT.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 178,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "31273777"
      ]
     },
     "execution_count": 178,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "all_pinyin_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 179,
   "metadata": {},
   "outputs": [],
   "source": [
    "min_frequences = min([f for _, f in PINYIN_COUNT.items()])\n",
    "\n",
    "def prob_one_gram(word):\n",
    "    if word in PINYIN_COUNT:\n",
    "        return PINYIN_COUNT[word] / all_pinyin_count\n",
    "    else:\n",
    "        return min_frequences / all_pinyin_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 180,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.003060039725933967"
      ]
     },
     "execution_count": 180,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prob_one_gram('qing')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 241,
   "metadata": {},
   "outputs": [],
   "source": [
    "PINYIN_3_GRAM = [''.join(CLEAN_PINYIN[i:i+3]) for i in range(len(CLEAN_PINYIN) - 2)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 242,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "31273775"
      ]
     },
     "execution_count": 242,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(PINYIN_3_GRAM)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 243,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['ciwaizi',\n",
       " 'waiziben',\n",
       " 'zibenzhou',\n",
       " 'benzhouyue',\n",
       " 'zhouyueri',\n",
       " 'yueriqi',\n",
       " 'riqichu',\n",
       " 'qichuxiao',\n",
       " 'chuxiaomi',\n",
       " 'xiaomishou']"
      ]
     },
     "execution_count": 243,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "PINYIN_3_GRAM[:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 244,
   "metadata": {},
   "outputs": [],
   "source": [
    "PINYIN_3_GRAM_COUNTER = Counter(PINYIN_3_GRAM)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 245,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('xinhuashe', 144468),\n",
       " ('nxinhua', 88145),\n",
       " ('nianyueri', 63509),\n",
       " ('nwaidai', 62323),\n",
       " ('daierxian', 61386),\n",
       " ('waidaier', 61385),\n",
       " ('yuerin', 52552),\n",
       " ('nyueri', 50890),\n",
       " ('huashezhao', 50469),\n",
       " ('shezhaopian', 50413)]"
      ]
     },
     "execution_count": 245,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "PINYIN_3_GRAM_COUNTER.most_common(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 246,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_max_length(my_dic: dict) -> int:\n",
    "    return len(max(my_dict, key=lambda x: len(x)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 247,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'shuangshuangchuang'"
      ]
     },
     "execution_count": 247,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max(PINYIN_3_GRAM_COUNTER, key=lambda x:len(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 327,
   "metadata": {},
   "outputs": [],
   "source": [
    "def known(words, my_dict):\n",
    "    \"\"\"\n",
    "    @param: words - list\n",
    "    @return: the pinyin words we have noticed.\n",
    "    \"\"\"\n",
    "    return {w for w in words if w in my_dict}\n",
    "\n",
    "def get_corrects(word, my_dict):\n",
    "    \"\"\"Find the most possible pinyin based on edit distance\"\"\"\n",
    "    # Prefer edit distance 0, then 1, then 2; otherwise default to word itself\n",
    "    \n",
    "    candicates = (known(edits0(word), my_dict) or\n",
    "                  known(edits1(word), my_dict) or\n",
    "                  known(edits2(word), my_dict)\n",
    "                 )\n",
    "    if candicates:\n",
    "        return max(candicates, key=my_dict.get)\n",
    "    else:\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 340,
   "metadata": {},
   "outputs": [],
   "source": [
    "def reverse_max_split(text: str, my_dict: dict) -> list:\n",
    "    result = []\n",
    "    window_size = get_max_length(my_dict)\n",
    "    index = len(text)\n",
    "    while index > 0:\n",
    "        for size in range(window_size, 0, -1):\n",
    "            if index - size < 0:\n",
    "                continue\n",
    "            piece = text[(index-size):index]\n",
    "            correct = 0\n",
    "            if len(piece) <= 3: # 如果是长度小于3的拼音词语，就选择使用 1-gram的词典\n",
    "                correct = get_corrects(piece, PINYIN_COUNT)\n",
    "            else:\n",
    "                correct = get_corrects(piece, my_dict)\n",
    "            if correct == 0:\n",
    "                continue\n",
    "            else:\n",
    "                result.append(correct)\n",
    "                if text.startswith(correct): # 判断text是否是以修正后的单词为开头的\n",
    "                    index = 0\n",
    "                    break\n",
    "                index -= len(correct) # 这里有一个问题，不能直接减去size，而是需要减去修正后的词语的长度-1\n",
    "                break            \n",
    "            index -= 1\n",
    "            result.append(piece)\n",
    "    return ''.join(result[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 346,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'woxiangshangqinghuadaxue'"
      ]
     },
     "execution_count": 346,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reverse_max_split('woxiangshangqinnghuadaxeu', PINYIN_3_GRAM_COUNTER)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 345,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'woxiangwozhendehenxihuanni'"
      ]
     },
     "execution_count": 345,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reverse_max_split('woxiangwozhendehenxihnanin', PINYIN_3_GRAM_COUNTER)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 348,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'pinying'"
      ]
     },
     "execution_count": 348,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reverse_max_split('pniyign', PINYIN_COUNT)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 总结\n",
    "在此次作业中，在对拼音句子进行分词时，尝试了多种分词方法，最后选择了逆向最大分词算法。\n",
    "\n",
    "此次作业测试数据较少，只是构思一些解决方法并尝试，后续需要整理更好的词典文件以及尝试其他更有效的分词算法来进行尝试，以便能达到一个更好的修正效果。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.7.4 64-bit ('AIs': pipenv)",
   "language": "python",
   "name": "python37464bitaispipenv05b87d701faf4fb2be1b80c713e5b80e"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
